package swardToOffer.method_4_dp_or_greedy;

/**
 * @Author ChanZany
 * @Date 2021/5/20 18:51
 * @Version 1.0
 * 思路：
 * 每次剪绳子都面临着多个选择，而总有一个选择是最优的
 * 状态方程：f(n)表示把长度为n的绳子剪成若干段后各段长度乘积的最大值
 * 当n<4 f(1)=0,f(2)=1,f(3)=2
 * 当n>=4 g(n)=g(i)g(n-i),g(3)=3,g(2)=2,g(1)=1
 */
// 面试题14：剪绳子
// 题目：给你一根长度为n绳子，请把绳子剪成m段（m、n都是整数，n>1并且m≥1）。
// 每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]*k[1]*…*k[m]可能的最大乘
// 积是多少？例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此
// 时得到最大的乘积18。

public class CuttingRope {
    int maxProductAfterCutting(int n) {
        if (n < 2) return 0;
        if (n == 2) return 1;
        if (n == 3) return 2;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 3;
        int max = 0;
        for (int i = 4; i < n + 1; i++) {
            for (int j = 1; j <= i / 2; j++) {
                int tmp = dp[j] * dp[i - j];
                max = Math.max(tmp, max);
            }
            dp[i] = max;
        }
        return dp[n];
    }

    //贪婪算法，当n>=5时，尽可能多地剪长度为3的绳子，当剩下的绳子为4的时候，把绳子剪成两端长度为2的绳子
    int maxProductAfterCutting2(int n) {
        if (n < 2) return 0;
        if (n == 2) return 1;
        if (n == 3) return 2;
        int max = 0;
        int n3 = n / 3;
        int remain = n - n3 * 3;
        if (remain == 1) {
            n3 = -1;
        }
        int n2 = (n - n3 * 3) / 2;
        return (int) Math.pow(3, n3) * (int) Math.pow(2, n2);

    }


    public static void main(String[] args) {
        CuttingRope Main = new CuttingRope();
        System.out.println(Main.maxProductAfterCutting(6));
        System.out.println(Main.maxProductAfterCutting2(6));
    }

}
